package lhc.alg.top100;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * description: https://leetcode.cn/problems/valid-parentheses/submissions/
 *  有效的括号
 * author: hongchen.liao
 * date:  2022/9/25
 */
public class _20_ {

    class Solution {
        public boolean isValid(String s) {
            Map<Character, Character> memo = new HashMap<>(){{
                put(']','[');
                put('}','{');
                put(')','(');
            }};
            Deque<Character> stack = new LinkedList<>();
            for(char ch : s.toCharArray()){
                if(memo.containsKey(ch)){
                    if(stack.size() == 0 || memo.get(ch) != stack.peek()){
                        return false;
                    }
                    stack.poll();
                }else{
                    stack.push(ch);
                }
            }
            return stack.isEmpty();
        }
    }

}
